package test.day04;

public class LinkedListCycle {
	static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
	
	public static ListNode detectCycle(ListNode head) {
		ListNode slow = head;
		ListNode fast = head;
		while (fast != null && fast.next != null) {
			slow = slow.next;
			fast = fast.next.next;
			if (slow == fast) {// 有环
				ListNode index1 = fast;
				ListNode index2 = head;
				// 两个指针，从头结点和相遇结点，各走一步，直到相遇，相遇点即为环入口
				while (index1 != index2) {
					index1 = index1.next;
					index2 = index2.next;
				}
				return index1;
			}
		}
		return null;
	}

	public static void main(String[] args) {
		ListNode one = new ListNode(3);
		ListNode two = new ListNode(2);
		ListNode three = new ListNode(0);
		ListNode four = new ListNode(4);
		one.next = two;
		two.next = three;
		three.next = four;
		four.next = two;

		System.out.println(detectCycle(one).val);
	}
}
